package com.fh.twopointers;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * @author fuhao
 * @date 2025/10/14 22:14
 */
public class T16ThreeSumClosest {
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            // 1. 对数组进行排序
            Arrays.sort(nums);
            // 2. 初始化最接近的和，可以先设为前三个元素的和
            int closestSum = nums[0] + nums[1] + nums[2];

            // 3. 遍历数组，固定第一个数 nums[i]
            for (int i = 0; i < nums.length - 2; i++) {
                // （可选优化）跳过重复的第一个数，避免重复计算
                // if (i > 0 && nums[i] == nums[i - 1]) continue;

                // 4. 初始化双指针
                int left = i + 1;
                int right = nums.length - 1;

                while (left < right) {
                    // 计算当前三数之和
                    int currentSum = nums[i] + nums[left] + nums[right];

                    // 如果当前和等于目标值，直接返回
                    if (currentSum == target) {
                        return target;
                    }

                    // 如果当前和更接近目标值，更新 closestSum
                    if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                        closestSum = currentSum;
                    }

                    // 根据当前和与目标值的大小关系移动指针
                    if (currentSum < target) {
                        left++; // 需要更大的和
                        // （可选优化）跳过重复的左指针值
                        // while (left < right && nums[left] == nums[left - 1]) left++;
                    } else {
                        right--; // 需要更小的和
                        // （可选优化）跳过重复的右指针值
                        // while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
            }
            return closestSum;
        }
    }
}
